{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Make Lexicographically Smallest Array by Swapping Elements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: lexicographicallySmallestArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #交换得到字典序最小的数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0 </strong>开始的 <strong>正整数</strong> 数组 <code>nums</code> 和一个 <strong>正整数</strong> <code>limit</code> 。</p>\n",
    "\n",
    "<p>在一次操作中，你可以选择任意两个下标 <code>i</code> 和 <code>j</code>，<strong>如果</strong> 满足 <code>|nums[i] - nums[j]| &lt;= limit</code> ，则交换 <code>nums[i]</code> 和 <code>nums[j]</code> 。</p>\n",
    "\n",
    "<p>返回执行任意次操作后能得到的 <strong>字典序最小的数组</strong><em> </em>。</p>\n",
    "\n",
    "<p>如果在数组 <code>a</code> 和数组 <code>b</code> 第一个不同的位置上，数组 <code>a</code> 中的对应元素比数组 <code>b</code> 中的对应元素的字典序更小，则认为数组 <code>a</code> 就比数组 <code>b</code> 字典序更小。例如，数组 <code>[2,10,3]</code> 比数组 <code>[10,2,3]</code> 字典序更小，下标 <code>0</code> 处是两个数组第一个不同的位置，且 <code>2 &lt; 10</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,5,3,9,8], limit = 2\n",
    "<strong>输出：</strong>[1,3,5,8,9]\n",
    "<strong>解释：</strong>执行 2 次操作：\n",
    "- 交换 nums[1] 和 nums[2] 。数组变为 [1,3,5,9,8] 。\n",
    "- 交换 nums[3] 和 nums[4] 。数组变为 [1,3,5,8,9] 。\n",
    "即便执行更多次操作，也无法得到字典序更小的数组。\n",
    "注意，执行不同的操作也可能会得到相同的结果。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,7,6,18,2,1], limit = 3\n",
    "<strong>输出：</strong>[1,6,7,18,1,2]\n",
    "<strong>解释：</strong>执行 3 次操作：\n",
    "- 交换 nums[1] 和 nums[2] 。数组变为 [1,6,7,18,2,1] 。\n",
    "- 交换 nums[0] 和 nums[4] 。数组变为 [2,6,7,18,1,1] 。\n",
    "- 交换 nums[0] 和 nums[5] 。数组变为 [1,6,7,18,1,2] 。\n",
    "即便执行更多次操作，也无法得到字典序更小的数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,7,28,19,10], limit = 3\n",
    "<strong>输出：</strong>[1,7,28,19,10]\n",
    "<strong>解释：</strong>[1,7,28,19,10] 是字典序最小的数组，因为不管怎么选择下标都无法执行操作。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= limit &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [make-lexicographically-smallest-array-by-swapping-elements](https://leetcode.cn/problems/make-lexicographically-smallest-array-by-swapping-elements/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [make-lexicographically-smallest-array-by-swapping-elements](https://leetcode.cn/problems/make-lexicographically-smallest-array-by-swapping-elements/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,5,3,9,8]\\n2', '[1,7,6,18,2,1]\\n3', '[1,7,28,19,10]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums2 = copy.deepcopy(nums)\n",
    "        nums2.sort()\n",
    "        ls = [[] for _ in range(n+1)]\n",
    "        ptrs = [0 for _ in range(n + 1)]\n",
    "        min_val= [9999999999 for _ in range(n + 1)]\n",
    "        ptr = 0\n",
    "        ls[0].append(nums2[0])\n",
    "        for i in range(1,n):\n",
    "            if nums2[i] - nums2[i-1] <= limit:\n",
    "                ls[ptr].append(nums2[i])\n",
    "            else:\n",
    "                ptr += 1\n",
    "                ls[ptr].append(nums2[i])\n",
    "        # print(ls)\n",
    "        for i in range(n):\n",
    "            if len(ls[i]) != 0:\n",
    "                ls[i].sort()\n",
    "                min_val[i] =ls[i][0]\n",
    "        for i in range(n):\n",
    "            val = nums[i]\n",
    "            index =bisect.bisect_left(min_val,val)\n",
    "            if min_val[index] > val:\n",
    "                index -= 1\n",
    "            # print(index)\n",
    "            ptrto = ptrs[index]\n",
    "            nums[i] = ls[index][ptrto]\n",
    "            ptrs[index] += 1\n",
    "        return nums\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:\n",
    "        nums_pair=sorted(zip(nums,range(len(nums))))\n",
    "        arr=[]\n",
    "        pre=nums_pair[0][0]\n",
    "        for k in nums_pair:\n",
    "            if len(arr) == 0 or k[0] - pre <= limit:\n",
    "                arr.append(k)\n",
    "            else:\n",
    "                for i,index in enumerate(sorted([x[1] for x in arr])):\n",
    "                    nums[index]=arr[i][0]\n",
    "                arr = [k]\n",
    "            pre = k[0]\n",
    "        for i,index in enumerate(sorted([x[1] for x in arr])):\n",
    "            nums[index]=arr[i][0]\n",
    "        arr = [k]\n",
    "        return nums\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:\n",
    "        x=sorted([(i,v) for i,v in enumerate(nums)],key=lambda x:x[1])\n",
    "        ret=[0]*len(nums)\n",
    "        pos=[x[0][0]]\n",
    "        vs=[x[0][1]]\n",
    "        def f():\n",
    "            pos.sort()\n",
    "            for j in range(len(pos)): ret[pos[j]]=vs[j]\n",
    "        for i in range(1,len(x)):\n",
    "            idx,v=x[i]\n",
    "\n",
    "            if v-x[i-1][1]<=limit:\n",
    "                pos.append(idx)\n",
    "                vs.append(v)\n",
    "            else:\n",
    "                f()\n",
    "                pos=[idx]\n",
    "                vs=[v]\n",
    "        f()\n",
    "        return ret\n",
    "\n",
    "\n",
    "    \n",
    "\n",
    "            \n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        idx_map = sorted(zip(nums, list(range(n))))\n",
    "        print(idx_map)\n",
    "\n",
    "        res = [0] * n\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            start = i\n",
    "            while i + 1 < n and idx_map[i + 1][0] - idx_map[i][0] <= limit:\n",
    "                i += 1\n",
    "\n",
    "            end = i\n",
    "            selected_idx = [x[1] for x in idx_map[start:end + 1]]\n",
    "            selected_idx.sort()\n",
    "            print(selected_idx)\n",
    "            for idx_diff in range(end - start + 1):\n",
    "                res[selected_idx[idx_diff]] = idx_map[idx_diff + start][0]\n",
    "            i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:\n",
    "        aux = [(x,i) for i,x in enumerate(nums)]\n",
    "        aux.sort()\n",
    "\n",
    "        val = []\n",
    "        index = []\n",
    "        cur = aux[0][0]\n",
    "        n = len(nums)\n",
    "        ans = [0] * n\n",
    "        aux.append((inf,inf))\n",
    "        for x,i in aux:\n",
    "            if x - cur <= limit:\n",
    "                val.append(x)\n",
    "                index.append(i)\n",
    "            if x - cur > limit:\n",
    "                val.sort()\n",
    "                index.sort()\n",
    "                for _index, _val in zip(index,val):\n",
    "                    ans[_index] = _val\n",
    "                val = [x]\n",
    "                index = [i]\n",
    "            cur = x\n",
    "        \n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:\n",
    "        x=[]\n",
    "        for i,v in enumerate(nums):\n",
    "            x.append((i,v))\n",
    "        x.sort(key=lambda x:x[1])\n",
    "        ret=[0]*len(nums)\n",
    "        pos=[]\n",
    "        vs=[]\n",
    "        for i in range(len(x)):\n",
    "            idx,v=x[i]\n",
    "            if i:\n",
    "                if v-x[i-1][1]<=limit:\n",
    "                    pos.append(idx)\n",
    "                    vs.append(v)\n",
    "                else:\n",
    "                    pos.sort()\n",
    "                    for j in range(len(pos)):\n",
    "                        ret[pos[j]]=vs[j]\n",
    "                    pos=[idx]\n",
    "                    vs=[v]\n",
    "            else:\n",
    "                pos=[idx]\n",
    "                vs=[v]\n",
    "        pos.sort()\n",
    "        for j in range(len(pos)):\n",
    "            ret[pos[j]]=vs[j]\n",
    "        return ret\n",
    "\n",
    "\n",
    "    \n",
    "\n",
    "            \n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "所有满足 |nums[i] - nums[j]| <= limit 的 num 都可以任意交换，我们称这些可以任意交换的 num 构成了连通块。\n",
    "\n",
    "nums 中可能存在多个连通块，由于一个连通块内的 num 可以任意交换，所以我们可以将一个连通块内的 num 从小到大排序，再放回连通块所在位置，这样就使得连通块内的字典序最小。\n",
    "\n",
    "对每个连通块执行相同的操作，就能使得整体的连通块最小。\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums_sorted_in_idx = sorted(zip(nums, range(n)))\n",
    "        print(nums_sorted_in_idx)\n",
    "\n",
    "        i = 0\n",
    "        ans = [0]*n\n",
    "        while i < n:\n",
    "            j = i + 1\n",
    "            while j < n and nums_sorted_in_idx[j][0] - nums_sorted_in_idx[j-1][0] <= limit:\n",
    "                j += 1\n",
    "            sub = nums_sorted_in_idx[i:j]\n",
    "            sub_idx_sorted = sorted(i for (_, i) in sub)\n",
    "            for (idx, (num, _)) in zip(sub_idx_sorted, sub):\n",
    "                ans[idx] = num\n",
    "            i = j\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:\n",
    "        nums_sort = [[nums[i], i] for i in range(len(nums))]\n",
    "        nums_sort = sorted(nums_sort,key=lambda x:x[0])\n",
    "\n",
    "        ans = [0] * len(nums)\n",
    "        pre = 0\n",
    "        for i in range(1, len(nums_sort) + 1):\n",
    "            if i == len(nums) or nums_sort[i][0] - nums_sort[i - 1][0] > limit :\n",
    "                need_locate = []\n",
    "                for j in range(pre, i):\n",
    "                    need_locate.append(nums_sort[j][1])\n",
    "                need_locate.sort()\n",
    "                for j in range(len(need_locate)):\n",
    "                    ans[need_locate[j]] = nums_sort[pre + j][0]\n",
    "                pre = i\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:\r\n",
    "        n = len(nums)\r\n",
    "        ans = [0] * n\r\n",
    "\r\n",
    "        lst = [(num, idx) for idx, num in enumerate(nums)]\r\n",
    "        lst.sort()\r\n",
    "\r\n",
    "        i = 0\r\n",
    "        while i < n:\r\n",
    "            num, idx = lst[i]\r\n",
    "            hp_idx = []\r\n",
    "            hp_num = []\r\n",
    "            heappush(hp_idx, idx)\r\n",
    "            heappush(hp_num, num)\r\n",
    "            j = i + 1\r\n",
    "            while j < n and lst[j][0] - lst[j-1][0] <= limit:\r\n",
    "                heappush(hp_idx, lst[j][1])\r\n",
    "                heappush(hp_num, lst[j][0])\r\n",
    "                j += 1\r\n",
    "            while hp_idx:\r\n",
    "                ans[heappop(hp_idx)] = heappop(hp_num)\r\n",
    "            i = j\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        pairs=[[nums[i],i] for i in range(0,n)]\n",
    "        pairs.sort()\n",
    "        q=[pairs[0]]\n",
    "        res=[0 for _ in range(0,n)]\n",
    "        def deal(q,res):\n",
    "            n = len(q)\n",
    "            idx = [0 for _ in range(0,n)]\n",
    "            for i in range(0,n):\n",
    "                idx[i]=q[i][1]\n",
    "            idx.sort()\n",
    "            for i in range(0,n):\n",
    "                res[idx[i]]=q[i][0]\n",
    "        for i in range(1,n):\n",
    "            if pairs[i][0]-pairs[i-1][0]<=limit:\n",
    "                q.append(pairs[i])\n",
    "            else:\n",
    "                deal(q,res)\n",
    "                q=[pairs[i]]\n",
    "        deal(q,res)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:\n",
    "        a=sorted(nums)\n",
    "        n=len(a)\n",
    "        b=[]\n",
    "        for i in range(n):\n",
    "            b.append([i,nums[i]])\n",
    "        b=sorted(b,key=lambda x:x[1])\n",
    "        c=[]\n",
    "        ans=[0]*n\n",
    "        for i in range(n):\n",
    "            print(b[i][1])\n",
    "        i=0\n",
    "        while i<n:\n",
    "            st=i\n",
    "            i+=1\n",
    "            arr=[b[st][0]]\n",
    "            while i<n and b[i][1]-b[i-1][1]<=limit:\n",
    "                arr.append(b[i][0])\n",
    "                i+=1\n",
    "            arr=sorted(arr)\n",
    "            for k,(_,j) in zip(arr,b[st:i]):\n",
    "                ans[k]=j\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:\n",
    "        num_sort = list(zip(nums,list(range(len(nums)))))\n",
    "        num_sort.sort()\n",
    "        ans = [0]*len(nums)\n",
    "        group = []\n",
    "        cur = []\n",
    "        for i in num_sort:\n",
    "            if not cur:\n",
    "                cur.append(i)\n",
    "            else:\n",
    "                if i[0]-cur[-1][0]<=limit:\n",
    "                    cur.append(i)\n",
    "                else:\n",
    "                    group.append(cur)\n",
    "                    cur=[]\n",
    "                    cur.append(i)\n",
    "        if cur:\n",
    "            group.append(cur)\n",
    "        for g in group:\n",
    "            pos = []\n",
    "            for i in g:\n",
    "                pos.append(i[1])\n",
    "            pos.sort()\n",
    "            for i in range(len(g)):\n",
    "                ans[pos[i]] = g[i][0]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        vals = []\n",
    "        for i,x in enumerate(nums):\n",
    "            vals.append((x,i))\n",
    "        vals.sort()\n",
    "        ans = nums[:]\n",
    "        l,r = 0,1\n",
    "        while r < n:\n",
    "            while r < n and vals[r][0]-vals[r-1][0] <= limit:\n",
    "                r += 1\n",
    "            vs, idxs = zip(*vals[l:r])\n",
    "            for idx,v in zip(sorted(idxs), vs):\n",
    "                ans[idx] = v\n",
    "            l,r = r,r+1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
